package 单周赛.september;

import util.ListNode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author xudongfu
 * @date 2024/07/14
 */
public class 第406场单周赛 {


    /**
     * 贪心
     * 从前往后遍历，如果奇偶性相同，且后面一个字符 < 前一个字符，那么交换顺序
     */
    public String getSmallestString(String s) {

        char[] chars = s.toCharArray();

        for (int i = 1; i < chars.length; i++) {
            if ((chars[i] - '0') % 2 == (chars[i - 1] - '0') % 2 &&
                    chars[i] < chars[i - 1]) {
                char t = chars[i];
                chars[i] = chars[i - 1];
                chars[i - 1] = t;
                break;
            }
        }
        return new String(chars);
    }

    /**
     * 模拟
     * 小技巧：创建一个虚拟头节点
     * 或许可以原地删除元素
     */
    public ListNode modifiedList(int[] nums, ListNode head) {
        ListNode tempHeader = new ListNode(-1);
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        ListNode curNode = tempHeader;
        while (head != null) {
            if (set.contains(head.val)) {
                head = head.next;
                continue;
            }
            curNode.next = new ListNode(head.val);
            curNode = curNode.next;

            head = head.next;
        }

        return tempHeader.next;
    }

    /**
     * 贪心
     * 优先切在垂直或横向花费最大的一刀
     * 在垂直方向切刀之后，下一个在横向切的时候加一倍的花费，反之亦然
     */
    public int minimumCost3(int m, int n, int[] horizontalCut, int[] verticalCut) {

        int ans = 0;
        int h = 1, v = 1;
        Arrays.sort(horizontalCut);
        Arrays.sort(verticalCut);

        int hIdx = horizontalCut.length - 1, vIdx = verticalCut.length - 1;

        while (hIdx >= 0 || vIdx >= 0) {

            if (hIdx < 0) {
                ans += verticalCut[vIdx] * h;
                vIdx--;
                v++;
                continue;
            }
            if (vIdx < 0) {
                ans += horizontalCut[hIdx] * v;
                hIdx--;
                h++;
                continue;
            }

            if (horizontalCut[hIdx] > verticalCut[vIdx]) {
                ans += horizontalCut[hIdx] * v;
                hIdx--;
                h++;
            } else {
                ans += verticalCut[vIdx] * h;
                vIdx--;
                v++;
            }
        }

        return ans;
    }

    public long minimumCost4(int m, int n, int[] horizontalCut, int[] verticalCut) {
        long ans = 0;
        int h = 1, v = 1;
        Arrays.sort(horizontalCut);
        Arrays.sort(verticalCut);

        int hIdx = horizontalCut.length - 1, vIdx = verticalCut.length - 1;

        while (hIdx >= 0 || vIdx >= 0) {

            if (hIdx < 0) {
                ans += verticalCut[vIdx] * h;
                vIdx--;
                v++;
                continue;
            }
            if (vIdx < 0) {
                ans += horizontalCut[hIdx] * v;
                hIdx--;
                h++;
                continue;
            }

            if (horizontalCut[hIdx] > verticalCut[vIdx]) {
                ans += horizontalCut[hIdx] * v;
                hIdx--;
                h++;
            } else {
                ans += verticalCut[vIdx] * h;
                vIdx--;
                v++;
            }
        }

        return ans;
    }
}
